
import time

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        
        def backtrack(start, current_subset):
            # 添加当前子集到结果中（需要复制列表）
            result.append(current_subset[:])
            
            # 尝试添加后续元素
            for i in range(start, len(nums)):
                current_subset.append(nums[i])
                backtrack(i + 1, current_subset)
                current_subset.pop()
        
        backtrack(0, [])
        return result


def test_subsets():
    """测试子集算法"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        # 基础测试
        [],
        [1],
        [1, 2],
        [1, 2, 3],
        [1, 2, 3, 4],
        
        # 负数测试
        [-1, 0, 1],
        [-2, -1],
        
        # 较大数组
        [1, 2, 3, 4, 5],
        [0, 1, 2, 3, 4, 5, 6],
    ]
    
    print("子集算法测试结果")
    print("=" * 50)
    
    for i, nums in enumerate(test_cases, 1):
        print(f"\n测试 {i}:")
        print(f"输入: {nums}")
        
        # 测量时间
        start_time = time.time()
        result = solution.subsets(nums)
        end_time = time.time()
        
        print(f"输出: {result}")
        print(f"子集数量: {len(result)} (期望: {2**len(nums)})")
        print(f"执行时间: {(end_time - start_time)*1000:.2f} ms")
        
        # 简单验证
        if len(result) == 2**len(nums):
            print("✅ 通过")
        else:
            print("❌ 失败")


def performance_test():
    """性能测试"""
    solution = Solution()
    
    print("\n性能测试")
    print("=" * 30)
    
    for n in range(1, 16):
        nums = list(range(1, n + 1))
        
        start_time = time.time()
        result = solution.subsets(nums)
        end_time = time.time()
        
        time_ms = (end_time - start_time) * 1000
        
        print(f"n={n:2d} | 子集数:{len(result):5d} | 时间:{time_ms:6.2f}ms")


if __name__ == "__main__":
    test_subsets()
    performance_test()
